package a08_回溯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * <p>
 * a05_电话号码的字母组合
 * </p>
 *
 * @author flyduck
 * @since 2024/12/30
 */
public class a05_电话号码的字母组合 {

    public static void main(String[] args) {
        a05_电话号码的字母组合 test = new a05_电话号码的字母组合();
        List<String> list = test.letterCombinations("23");
        System.out.println(list);
    }
    public List<String> letterCombinations(String digits) {
        char[] digitsCharArray = digits.toCharArray();
        int[] digitsArray = new int[digitsCharArray.length];
        for (int i = 0; i < digitsCharArray.length; i++) {
            digitsArray[i] = Integer.valueOf(new Character(digitsCharArray[i]).toString());
        }
        String[] strArray = new String[]{
          "",
          "",
          "abc",
          "def",
          "ghi",
          "jkl",
          "mno",
          "pqrs",
          "tuv",
          "wxyz"
        };

        List<String> resultList = new ArrayList<>();
        LinkedList<Character> path = new LinkedList<>();
        if(digits == null || "".equals(digits)){
            return resultList;
        }
        traversal(resultList, path, strArray, digitsArray, 0);
        return resultList;
    }

    private void traversal(List<String> resultList,
                           LinkedList<Character> path,
                           String[] strArray,
                           int[] digitsArray,
                           int digitsArrayIdx){
        if (path.size() == digitsArray.length) {
            String collect = path.stream().map(c -> c.toString()).collect(Collectors.joining(""));
            resultList.add(collect);
            return;
        }

        char[] chars = strArray[digitsArray[digitsArrayIdx]].toCharArray();
        for (int i = 0; i < chars.length; i++) {
            path.add(chars[i]);
            traversal(resultList, path, strArray, digitsArray, digitsArrayIdx + 1);
            path.removeLast();
        }
    }
}
